<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Bit_Reducer.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="This module generalizes the usual 2-input Boolean functions to their n-input reductions, which are interesting and useful:">
<title>Bit Reducer</title>
</head>
<body>

<p class="inline bordered"><b><a href="./Bit_Reducer.v">Source</a></b></p>
<p class="inline bordered"><b><a href="./legal.html">License</a></b></p>
<p class="inline bordered"><b><a href="./index.html">Index</a></b></p>

<h1>Boolean Bit Reducer</h1>
<p>This module generalizes the usual 2-input Boolean functions to their
 n-input reductions, which are interesting and useful:</p>
<ul>
<li>Trivially calculate <em>any of these</em> (OR) or <em>all of these</em> (AND) conditions and their negations.</li>
<li>Calculate even/odd parity (XOR/XNOR)</li>
<li>Selectively invert some of the inputs and you can decode any intermediate condition you care to.</li>
</ul>
<p>Beginners can use this module to implement any combinational logic while
 knowing a minimum of Verilog (no always blocks, no blocking/non-blocking
 statements, only wires, etc...).</p>
<p>Experts generally would not use this module. It's far simpler to <a href="./verilog.html#boolean">express
 the desired conditions directly</a> in Verilog.
 However, there are a few reasons to use it:</p>
<ul>
<li>It will keep your derived schematics clean of multiple random little gates, and generally preserve the schematic layout.</li>
<li>If there is a specific meaning to this reduction, you can name the module descriptively.</li>
<li>It will make clear which logic gets moved, in or out of that level of hierarchy, by optimization or retiming post-synthesis.</li>
</ul>
<h2>Differences with Verilog Reduction Operators</h2>
<p>The specification of reduction operators in Verilog (2001 or SystemVerilog)
 contains an error which does not perform a true reduction when the Boolean
 operator in the reduction contains an inversion (NOR, NAND, XNOR). Instead,
 the operator will perform a non-inverting reduction (e.g.: XOR), then
 invert the final result. For example, <code>A = ~^B;</code> (XNOR reduction) should
 perform the following:</p>
<pre>(((B[0] ~^ B[1]) ~^ B[2]) ~^ B[3) ... </pre>

<p>but instead performs the following, which is not always equivalent:</p>
<pre>~(B[0] ^ B[1] ^ B[2] ^ B[3 ...)</pre>

<p>To implement the correct logical behaviour, we do the reduction in a loop
 using the alternate implementation described in the <a href="./Word_Reducer.html">Word
 Reducer</a> module.  The differences were
 <a href="https://twitter.com/wren6991/status/1259098465835106304">spotted</a> by Luke
 Wren (<a href="https://twitter.com/wren6991">@wren6991</a>).</p>
<h2>Errors, Verilog Strings, and Linter Warnings</h2>
<p>There's no clean way to stop the CAD tools if the <code>OPERATION</code> parameter is
 missing or incorrect. Here, the logic doesn't get generated, which will
 fail pretty fast...</p>
<p>The <code>OPERATION</code> parameter also reveals how strings are implemented in
 Verilog: just a sequence of 8-bit bytes. Thus, if we give <code>OPERATION</code>
 a value of <code>"OR"</code> (16 bits), it must first get compared against <code>"AND"</code> (24
 bits) and <code>"NAND"</code> (32 bits). The Verilator linter throws a width mismatch
 warning at those first two comparisons, of course. Width warnings are
 important to spot bugs, so to keep them relevant we carefully disable width
 checks only during the parameter tests.</p>

<pre>
`default_nettype none

module <a href="./Bit_Reducer.html">Bit_Reducer</a>
#(
    parameter OPERATION     = "",
    parameter INPUT_COUNT   = 0
)
(
    input   wire    [INPUT_COUNT-1:0]   bits_in,
    output  reg                         bit_out
);

    initial begin
        bit_out = 1'b0;
    end
</pre>

<p>First, initialize the partial reduction storage. Each partial reduction
 must be stored in its own storage, else we describe a broken combinational
 loop.</p>
<p>To make the code clearer, <code>partial_reduction</code> is read and written in
 different <code>always</code> blocks, so the linter is confused and sees a potential
 combinational loop, which doesn't exist here because of the non-overlapping
 indices. So we disable that warning here.</p>

<pre>
    // verilator lint_off UNOPTFLAT
    reg [INPUT_COUNT-1:0] partial_reduction;
    // verilator lint_on  UNOPTFLAT

    integer i;

    initial begin
        for(i=0; i < INPUT_COUNT; i=i+1) begin
            partial_reduction[i] = 1'b0;
        end
    end
</pre>

<p>Then prime the partial reductions with the first input, and read out the
 result at the last partial reduction.</p>

<pre>
    always @(*) begin
        partial_reduction[0]    = bits_in[0];
        bit_out                 = partial_reduction[INPUT_COUNT-1];
    end
</pre>

<p>Finally, select the logic to instantiate based on the <code>OPERATION</code>
 parameter. Each partial reduction is the combination of the previous
 reduction and the current corresponding input bit.</p>

<pre>
    generate

        // verilator lint_off WIDTH
        if (OPERATION == "AND") begin : gen_and
        // verilator lint_on  WIDTH
            always @(*) begin
                for(i=1; i < INPUT_COUNT; i=i+1) begin
                    partial_reduction[i] = partial_reduction[i-1] & bits_in[i];
                end
            end
        end
        else
        // verilator lint_off WIDTH
        if (OPERATION == "NAND") begin : gen_nand
        // verilator lint_on  WIDTH
            always @(*) begin
                for(i=1; i < INPUT_COUNT; i=i+1) begin
                    partial_reduction[i] = ~(partial_reduction[i-1] & bits_in[i]);
                end
            end
        end
        else
        // verilator lint_off WIDTH
        if (OPERATION == "OR") begin : gen_or
        // verilator lint_on  WIDTH
            always @(*) begin
                for(i=1; i < INPUT_COUNT; i=i+1) begin
                    partial_reduction[i] = partial_reduction[i-1] | bits_in[i];
                end
            end
        end
        else
        // verilator lint_off WIDTH
        if (OPERATION == "NOR") begin : gen_nor
        // verilator lint_on  WIDTH
            always @(*) begin
                for(i=1; i < INPUT_COUNT; i=i+1) begin
                    partial_reduction[i] = ~(partial_reduction[i-1] | bits_in[i]);
                end
            end
        end
        else
        // verilator lint_off WIDTH
        if (OPERATION == "XOR") begin : gen_xor
        // verilator lint_on  WIDTH
            always @(*) begin
                for(i=1; i < INPUT_COUNT; i=i+1) begin
                    partial_reduction[i] = partial_reduction[i-1] ^ bits_in[i];
                end
            end
        end
        else
        // verilator lint_off WIDTH
        if (OPERATION == "XNOR") begin : gen_xnor
        // verilator lint_on  WIDTH
            always @(*) begin
                for(i=1; i < INPUT_COUNT; i=i+1) begin
                    partial_reduction[i] = ~(partial_reduction[i-1] ^ bits_in[i]);
                end
            end
        end

    endgenerate
endmodule
</pre>

<hr>
<p><a href="./index.html">Back to FPGA Design Elements</a>
<center><a href="https://fpgacpu.ca/">fpgacpu.ca</a></center>
</body>
</html>

